import collections


class Solution(object):
    def findTheCity(self, n, edges, distanceThreshold):
        d = collections.defaultdict(dict)
        for u, v, dist in edges:
            d[u][v] = dist
            d[v][u] = dist
        min_dist = float('inf')
        for u in range(n):
            p = [-1] * n
            p[u] = 0
            now = {u}
            s_set = set()
            while now:
                node = now.pop()
                for v in d[node]:
                    if p[node] + d[node][v] <= distanceThreshold and (p[v] == -1 or p[node] + d[node][v] < p[v]):
                        p[v] = p[node] + d[node][v]
                        now.add(v)
                        s_set.add(v)
            if len(s_set) <= min_dist:
                min_dist = len(s_set)
                min_index = u
        return min_index


data = Solution()
n = 5
edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]]
T = 2
print(data.findTheCity(n, edges, T))